from bisect import bisect_left, insort

from utils import floatcompare as compare, MAXFLOAT
from utils.copy import smartcopy, deepcopy_into

from cranesched.routing.geometry import Line


class Path(object):
    """This class is used to represent the trajectory of a crane in the warehouse's x-axis."""
    def __init__(self, time=0.0, position=0.0):
        self.clear(time, position)
        
    def clear(self, time=0.0, position=0.0):
        self.time = time
        self.position = position
        self.times = [time]
        self.positions = [position]
        self.segment_cache = dict()
        
    def __len__(self):
        return len(self.times)
        
    def __getitem__(self, index):
        if isinstance(index, slice):
            return zip(self.times[index], self.positions[index])
        return (self.times[index], self.positions[index])
        
    def __deepcopy__(self, memo):
        clone = smartcopy(self, memo, 
                          shallowcopy_attrs=("time", "position"), 
                          deepcopy_attrs=("times", "positions"))
        if memo.get("copy_segment_cache", True):
            clone.segment_cache = dict(self.segment_cache)
        else:
            clone.segment_cache = dict()
        return clone
        
    deepcopy = deepcopy_into
    
    def position_at(self, time):
        if time >= self.time:
            return self.position
        segment = self.segments_at(time)[0]
        return segment.y_at(time)
        
    def segments_at(self, time):
        """Given a time value, returns the segment (or two segments at boundary points) which 
        covers the specified time. Returns a list of one or two Segment objects."""
        return [self.segment(i) for i in self.segment_indices_at(time)]
        
    def new_segment_indices_at(self, time, lo=0, hi=None):
        times = self.times
        if hi is None:
            hi = len(times)
        if compare.lt(time, times[lo]) or compare.gt(time, times[hi-1]):
            raise ValueError("time value outside specified range")
        index = min(hi-2, bisect_left(times, time, lo, hi))
        if compare.lt(time, times[index]) and compare.eq(time, times[index-1]):
            index -= 1
        elif compare.gt(time, times[index]) and compare.eq(time, times[index+1]):
            index += 1
        if index > 0 and compare.eq(time, times[index]):
            return [index-1, index]
        return [index]

    def segment_indices_at(self, time, lo=0, hi=None):
        times = self.times
        if hi is None:
            hi = len(times)
        if compare.lt(time, times[lo]) or compare.gt(time, times[hi-1]):
            raise ValueError("time value outside specified range")
        index = bisect_left(times, time, lo, hi)
        if (index < len(times) - 2 and 
            #compare.gt(time, times[index]) and 
            compare.eq(time, times[index + 1])):
                # this is a fix to add floating point comparison 
                # tolerance, since bisect_left() does not have any
                index += 1
        if compare.eq(time, times[index]) and 0 < index < len(times) - 1:
            return [index - 1, index]
        return [max(0, index - 1)]
        
    def segment(self, index):
        """Given an integer index, return the corresponding segment in the path, e.g. 
        path.segment(0) will return the segment joining the first and second points in the path 
        (i.e. indices 0 and 1)."""
        if index < 0:
            index += len(self.times)
            if index < 0:
                raise IndexError("invalid index provided")
        try:
            return self.segment_cache[index]
        except KeyError:
            t, p = self.times, self.positions
            segment = Line.Segment(t[index], p[index], t[index + 1], p[index + 1])
            self.segment_cache[index] = segment
            return segment
            
    def append(self, time, position=None):
        if position is None:
            position = self.positions[-1]
        current_time = self.times[-1]
        if compare.leq(time, current_time):
            if compare.lt(time, current_time):
                raise ValueError("invalid time provided (less than current time)")
            if compare.neq(position, self.positions[-1]):
                raise ValueError("invalid position provided (leads to non-continuous path)")
        else:
            self.time = time
            self.position = position
            self.times.append(time)
            self.positions.append(position)
            
    def extend(self, points):
        """Given an iterable of (time, position) tuples, append them to the path in the given 
        order."""
        for time, position in points:
            self.append(time, position)
            
    def pop(self):
        segment_idx   = len(self.times) - 2
        result        = (self.times.pop(), self.positions.pop())
        self.time     = self.times[-1]
        self.position = self.positions[-1]
        if segment_idx in self.segment_cache:
            del self.segment_cache[segment_idx]
        return result
        
    def offset_position(self, delta):
        """Apply an offset 'delta' along the whole Path object. This operation works in-place."""
        self.positions = [position + delta for position in self.positions]
        self.position = self.positions[-1]
        self.segment_cache.clear()
        
    def offset_time(self, delta):
        """Apply an offset 'delta' to all times in Path object. This operation works in-place."""
        self.times = [time + delta for time in self.times]
        self.time = self.times[-1]
        self.segment_cache.clear()
        
    def intersection(self, line, index=1):
        """Returns a specific point of intersection between the given line or line segment and 
        the Path's line plot. The returned point is determined by index:
            a) index > 0, returns the index-th left-most intersection
            b) index < 0, returns the index-th right most intersection"""
        assert index != 0
        reverse = False
        if index < 0:
            reverse = True
            index *= -1
        iterator = self.intersections(line, reverse=reverse)
        for _ in xrange(index):
            try:
                point, segment = iterator.next()
            except StopIteration:
                return None
        return point, segment
        
    def intersections(self, line, reverse=False):
        """Computes all intersections (left-to-right default, right-to-left if 'reverse' is True) 
        of the Path's line plot with the argument line or line segment."""
        if compare.gt(line.xmin, self.times[-1]) or compare.lt(line.xmax, self.times[0]):
            return  # line segment is completely outside the path's bounds
        
        # we must check all segments if a full line was provided
        index0 = 0
        index1 = len(self.times) - 1
        step = +1
        # if the line is closed in any of its two ends, we can reduce 
        # the slice of the path where we check for intersections
        if compare.gt(line.xmin, self.times[0]):
            index0 = self.segment_indices_at(line.xmin)[0]
        if compare.lt(line.xmax, self.times[-1]):
            index1 = self.segment_indices_at(line.xmax, lo=index0)[-1] + 1
        # swap xrange indices and step if reverse is True
        if reverse:
            index0, index1 = index1 - 1, index0 - 1
            step = -1
        for index in xrange(index0, index1, step):
            segment = self.segment(index)
            point = segment.intersection(line)
            if point is not None:
                yield point, segment
                
    @staticmethod
    def multipath_intersections(paths, line, reverse=False):
        """An iterator over the intersections of the given line or line segment with a list of 
        Path objects."""
        pqueue = []
        index = 0
        def advance(path, iterator):
            try:
                point, segment = iterator.next()
            except StopIteration:
                return
            sortkey = point[0] if not reverse else -point[0]
            insort(pqueue, (sortkey, point, segment, path, iterator), lo=index)
            
        # fill pqueue with initial intersection from each path
        for path in paths:
            advance(path, path.intersections(line, reverse=reverse))
        # consume the intersections in order (left-to-right, ties w/ undefined order)    
        while index < len(pqueue):
            _, point, segment, path, iterator = pqueue[index]
            index += 1
            if index % 50 == 0:
                pqueue = pqueue[index:]
                index = 0   
            yield point, segment, path
            advance(path, iterator)
            
    def collisions(self, path, reverse=False):
        """Returns an iterator over the intersections of all segments of the two paths. Remaining 
        arguments take the same meaning as in intersections()."""
        i = 0
        j = len(self.times) - 1
        k = +1
        if compare.gt(path.times[0], self.times[0]):
            i = self.segment_indices_at(path.times[0])[0]
        if compare.lt(path.time, self.time):
            j = self.segment_indices_at(path.time, lo=i)[-1]
        if reverse:
            i, j, k = j-1, i-1, -1
        for l in xrange(i, j, k):
            segment1 = self.segment(l)
            for point, segment2 in path.intersections(segment1, reverse):
                yield point, segment1, segment2
                
    def collides(self, path, reverse=False):
        """Returns true if there is at least one collision between the two paths."""
        iterator = self.collisions(path, reverse)
        try:
            iterator.next()
        except StopIteration:
            return False
        return True
        
    def line_plot(self, target=None, **kwargs):
        from khronos.statistics.plotter import get_plotter
        
        to_restore = None
        if self.time >= MAXFLOAT:
            to_restore = self.times.pop(), self.positions.pop()
        plt = get_plotter(target)
        axes = plt.line_plot(self.times, self.positions, **kwargs)
        axes.set_xlabel("Time")
        axes.set_ylabel("Position")
        if to_restore is not None:
            self.times.append(to_restore[0])
            self.positions.append(to_restore[1])
        return axes
        
        
        
def _test():
    """A demo of all relevant features of the Path class."""
    import random
    random.seed(0)
    
    path = Path()
    for t in xrange(1, 101):
        path.append(t, random.randint(0, 100))
    axes = path.line_plot()
    
    segment = Line.Segment(0, 10, 100, 90)
    line = Line(0, 100, 1, 99)
    points = [point for point, _ in path.intersections(segment)]
    tmp = list(reversed([point for point, _  in path.intersections(segment, reverse=True)]))
    assert points == tmp; del tmp
    points2 = [point for point, _ in path.intersections(line)]
    axes.plot(segment.xs, segment.ys, color="green")
    axes.plot(line.xs, line.ys, color="green")
    axes.scatter([x for x, y in points], [y for x, y in points], color="red")
    axes.scatter([x for x, y in points2], [y for x, y in points2], color="yellow")
    
    above = path.deepcopy()
    above.offset_position(+10)
    above.line_plot(target=axes, color="pink")
    below = path.deepcopy()
    below.offset_position(-10)
    below.line_plot(target=axes, color="pink")
    axes.fill_between(path.times, y1=above.positions, y2=below.positions, color="pink", alpha=0.25)
    
    points = [p for p, _, _ in Path.multipath_intersections([above, below], segment)]
    for i in xrange(len(points) - 1):
        assert points[i][0] <= points[i+1][0]
    axes.scatter([x for x, y in points], [y for x, y in points], color="green")
    points2 = sorted([point for point, _ in above.intersections(segment)] +
                     [point for point, _ in below.intersections(segment)])
    assert points == points2
    
    points3 = [p for p, _, _ in Path.multipath_intersections([above, below], segment, reverse=True)]
    points3.reverse()
    assert points == points3
    
    ts, ps = [], []
    for i in (1, -1, 5, -5):
        result = path.intersection(segment, index=i)
        if result is not None:
            point, _ = result
            ts.append(point[0])
            ps.append(point[1])
    axes.scatter(ts, ps, color="purple", marker="v", s=100)
    
    ts, ps = [], []
    for i in xrange(100):
        ts.append(random.uniform(0, 100))
        ps.append(path.position_at(ts[-1]))
    axes.scatter(ts, ps, color="cyan", marker="+", s=100)
    axes.grid()
    axes.figure.plotter.update()
    return axes


